In a computer-based imaging system, data which describes an image is generated in a host computer, for example by means of a desktop publishing program, and then forwarded to an image generating device where it is converted into a format that can be used by the device. In an exemplary system, the image data from the host computer might be in the format of a high-level page description language (PDL). One example of a well-known PDL is PostScript. In the host computer, graphic commands from the desktop publishing program, or other suitable application program, are converted into PDL commands. These commands are sent to the printer which interprets them and determines which types of graphics operations are to be performed, such as draw a rectangle or a particular character of text. The interpretation process typically also determines associated graphic state arguments that apply to each object, such as color, font, size, and the like. This information is then converted into pixel display values which are stored in a frame buffer to represent the shapes and colors of the objects. The values in the frame buffer are used to control the operation of the active elements in a print engine, such as a laser diode in a laser printer or a print head in an inkjet printer, to form the image. The process of converting the high-level PDL commands into the frame buffer display values is known as rendering.
To increase the overall rate at which printing is carried out, particularly for complex documents containing different types of objects, the various steps of the rendering process might be pipelined. At one or more stages of the process, the image data is converted to an intermediate form which can be utilized more efficiently by the next stage. For example, in one well-known type of operation relating to laser printers, high-level graphics operations are determined from the PDL data, and stored in a display list from which they are provided to the stage which generates the individual pixel display values.
Typically, one of two different types of organization is employed to store data pertaining to objects and graphic states in the display list. In one form of organization, the objects are sorted by time, i.e., they are stored in the order in which they were drawn by the user. In the other form, the objects are sorted by their position in the image, with reference to the direction of output device processing, e.g., the scanning of a laser beam across a photosensitive element in a laser printer. Sorting by time offers the advantage that it preserves imaging order. If a later-created object overlaps an earlier created object, it will obscure some or all of the earlier-created objects in the final image (assuming the objects are opaque). The time-sorted display list inherently identifies the overlapping relationship of the objects without the need to store additional information pertaining thereto. However, the list of objects can jump from one location on the page to another and back, which can result in certain inefficiencies in some types of rendering implementations. When the display list is sorted by position, more efficient rendering can be carried out. However, this approach requires additional information to be stored in the list which identifies the relative depth, i.e., front-to-back relationship, of objects in the image.
Even with time-sorted display lists, the amount of information to be stored is a significant consideration for purposes of efficient memory allocation. More particularly, each entry in the display list represents a shape or a graphics state command, e.g., color, to be applied to subsequent entries. In addition to this image data, each entry has some associated overhead information. This overhead information might comprise a header which describes the type of entry, and a pointer or other reference to the next entry on the list. In doubly-linked lists, another pointer refers back to the previous entry on the list.
It is desirable to store image data in a display list, or other intermediate form of data storage, in a manner which provides the benefits of both time-sorted entries and position-sorted entries, without the limitations associated with each. It is also desirable to minimize the overall amount of information that is stored in a display list, to provide more efficient memory utilization.